package DataStructures.linkedlist;

/**
 * @author ：ALi
 * @date ：Created in 2021/10/31 20:28
 * @description：约瑟夫问题
 * @modified By：
 * @version: $
 */
public class JosepfuList {

    public static void main(String[] str){
        CircleSingleLinkedList cl = new CircleSingleLinkedList();
        cl.addBoy(125);
        cl.ShowBoy();

        System.out.println("-------------------------");
        cl.delectBoy(10,20,125);



    }



}

class Boy{
    private int no;
    private Boy next;
    public Boy(){

    }


    public Boy(int no){
        this.no = no;
    }
    /**
     * create by: ALi
     * description: get and set 方法
     * create time: 2021/10/31 20:30
     * @Param: null
     * @return
     */

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
class CircleSingleLinkedList{
    //创建一个first节点
    private Boy first = new Boy(-1);



    /**
     * create by: ALi
     * description: 添加节点
     * create time: 2021/10/31 20:33
     * @Param: nums 增加的节点个数
     * @return
     */
    public void addBoy(int nums){
        if(nums < 1){
            System.out.println("nums的值不存在");
            return;
        }

        //辅助节点（尾结点）
        Boy endBoy = first;
        for(int i = 1;i<=nums;i++){
            //根据编号创建小孩节点
            Boy boy = new Boy(i);
            //一个节点
            //因为这个first为-1，所以要先把第一个节点赋值给first刷题的时候不需要这样考虑
            if (i == 1){
                first = boy;
                first.setNext(first);
                endBoy = first;
            }else {
                //多个节点的情况
                endBoy.setNext(boy);
                boy.setNext(first);
                endBoy = boy;

            }
        }
    }

    public void ShowBoy(){
        //判断为空
        if (first == null){
            System.out.println("链表为空");
            return;
        }else {
            Boy temp = first;
            //辅助指针的next值不是first值
            //或者用do-while
            while(true){
                System.out.printf("编号：%d\n",temp.getNo());
                if(temp.getNext() == first){
                    break;
                }
                //temp后移
                temp = temp.getNext();
            }
        }
    }


    /**
     * create by: ALi
     * description: 删除节点（出圈）
     * create time: 2021/11/1 10:27
     * @Param: startNo 起点，countNum 出圈位置，nums 小孩个数
     * @return
     */
    public void delectBoy(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误");
            return;
        }
        Boy temp = first;

        //temp指向最后一个节点
        while (true) {
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }

        //让first移动到startNo处，temp依旧移动
        for (int i = 0; i < startNo - 1; i++) {
            temp = temp.getNext();
            first = first.getNext();
        }

        //移除多个为countNum-1倍数的节点
        while (true){
            if(temp == first){
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
                temp = temp.getNext();
                first = first.getNext();
            }
            System.out.printf("小孩%d出圈\n",first.getNo());
            //删除节点
            first = first.getNext();
            temp.setNext(first);
        }
        System.out.printf("小孩%d在圈中\n",first.getNo());

    }
}